1. Field of the Invention
The present invention relates to a technology for evaluating the location of a failure in a logic circuit. More particularly, the invention relates to a system, a method, a device, and a recording medium for evaluating the location of a failure, which are suitably used for the evaluation of the location of a failure in a logic circuit including gates defined in a hierarchical manner.
2. Description of the Related Art
A system for evaluating the location of a failure is designed to evaluate a path possibly having a failure propagated therethrough, which may satisfy an output pattern including a failure output, and then evaluates a location of the failure based on such information. For example, as described in Japanese Patent Laid-Open Hei 08 (1996)-146093 (Patent No. 2655105), Japanese Patent Laid-Open Hei 10 (1998)-062494, and so on, this system can be used as a part of the failure location evaluating system of a sequential circuit. A technology described in each of such publications provides a system for evaluating the location of a failure, which is based on a path tracing method for evaluating a failure propagation path from a failure output terminal in an input direction.
In the case of evaluating a failure propagation path, it is necessary to obtain a logical state for each of the nodes (a gate, a signal line, and a terminal) inside a circuit. Here, description will be made with reference to a specific circuit. FIG. 18 shows a benchmark circuit C17 composed only of NAND gates. Hereinbelow, with respect to the circuit shown in FIG. 18, a method for evaluating a failure propagation path with L22=1 and L23=1 is described based on a method for extracting a failure propagation path, which the inventor of the present invention disclosed in Japanese Patent Laid-Open Hei 11 (1999)-153646. In FIG. 18, a parenthesized numeral denotes an expected value of each signal line.
First, since there is no signal line state implied by L22=1 and L23=1, a signal line is retrieved to set a temporary logical value. According to the failure propagation path extracting method of the foregoing publication of Japanese Patent Laid-Open Hei 11 (1999)-153646, a temporary logical value is set on an input signal line of a gate connected to a failure signal line, a state of the gate having yet to be unestablished (unestablished gate).
FIG. 20 shows an IF-THEN operation (implication operation) in the input/output direction of a two-input NAND gate. When a logical value of an output signal line is xe2x80x9c1xe2x80x9d, and both of two logical values of the input signal lines are xe2x80x9cXxe2x80x9d, a logical value of either one of the input signal lines should be xe2x80x9c0xe2x80x9d. However, since it has yet to be established, the gate is determined to be an unestablished gate.
In the example shown in FIG. 18, a logical value xe2x80x9c0xe2x80x9d is temporarily set on L16, which is one of the input signal lines of a gate G23 connected to the failure signal line L23. With L16=0 being temporarily set, L2=1 and L11=1 are implicated by the IFTHEN operation of G16. Thereafter, the IF-THEN operation and the temporary setting of a logical value are repeated and, by temporarily setting logical values on the signal lines of two locations, three logical states are obtained as shown in the decision tree of FIG. 19. The obtained logical states inside the circuit describe the logical values of the respective signal lines in portions enclosed with squares of FIG. 19 in the order of (L1, L2, L3, L6, L7, L10, L11, L16, L19, L22, and L23). The underline below each logical value represents a failure propagation path, in which an expected value is different from the logical value.
Each signal line on the failure propagation path obtained by the foregoing method becomes a failure location candidate, which is an origin for propagating a failure state to the failure output of the logic circuit.
The foregoing publications of Japanese Patent Laid-Open Hei 08 (1996)-146093, and Patent Laid-Open Hei 10 (1998)-062494 disclose the method of deciding a priority order among a failure candidates by weighting a failure propagation path evaluated according to a rule. One example is given hereinbelow. It is assumed for example that a failure propagation path like that shown in FIG. 21 has been obtained. In this case, by calculating the number of failure output terminals as a weight, to which an error state may propagate, the parenthesized numerals are obtained as shown in FIG. 21 when a failure is present in each path.
This weight can be obtained by transmitting the information about a failure output terminal in an input direction. On a path p1, there is a possibility of propagating failures to four failure output terminals (F1 to F4), and a weight becomes a maximum value 4. Accordingly, it can be determined that the possibility of a failure present in the path p1 is high.
As can be understood from the foregoing, the following three processings must be carried out for each gate with regard to the process for evaluating the location of a failure based on path tracing:
(1) an IF-THEN operation in an input/output direction based on the function of each gate;
(2) determination of an unestablished gate, and retrieval of a signal line, a temporary logical value being set thereon; and
(3) transmission of information regarding a related failure output terminal to the input side.
It has conventionally been considered that when the location of a failure is evaluated based on path tracing by setting a logic circuit including a user-defined gate serving as a target, the user must prepare a database for each gate for realizing the above three processings, and incorporate the database in a system. For such a user-defined gate, a hierarchical circuitry for logic simulation has been prepared, whereas no databases, in which process for evaluating a failure location is defines, have not.
Consequently, when the number of user-defined gates is increased, the number of databases to be prepared becomes enormous, as a result, a great deal of time and labor are required. In addition, as in the case of a flip-flop (FF), complicated processing must be taken into consideration, where the logical state of an input/output terminal is extending over time points. Accordingly the preparation of databases by a failure analyzer, not a designer, is difficult.
In a circuit designing environment, for the user-defined gate, a hierarchical circuitry is described based on a hardware descriptive language such as Verilog or the like by a basic gate such as an AND, a NAND or the like to be evaluated, and kept in a library form. Thus, even those who are not circuit designers can carry out logic simulation.
Gate processing in the logic simulation can be realized only by an IF-THEN operation in an output direction. This is because a gate output logical state is uniquely set when a logical value of a gate input terminal is decided. However, determination of an unestablished gate necessary for the evaluation of a failure location, or transmission of information regarding a related failure output terminal cannot be realized only by such an IF-THEN operation in an output direction.
As is apparent from the foregoing, the following problems are inherent in the conventional a failure evaluating system.
A first problem is that a database dedicated to the process of evaluating the location of a failure needs to be created in the case of evaluating the location of a failure in the logic circuit including gates defined in a hierarchical manner.
This is because in the processing of each of the hierarchically defined gates for the evaluation of the location of a failure, the IF-THEN operation in the input/output direction, the retrieval of a signal line, a temporary logical value being set thereon, and the transmission of information regarding a failure terminal are essential, and only a database for a basic gate is prepared in the failure location evaluating device.
A second problem is that the gate library describing a circuitry composed of the basic gates, which have been prepared for the logic simulation, cannot be utilized for the process of evaluating the location of a failure.
This is because there is no method provided for realizing the three processings essential for the evaluation of the location of a failure, that is, the IF-THEN operation in the input/output direction, the retrieval of a signal line, a temporary logical value being set thereon, and the transmission of information regarding a failure terminal.
A third problem is that it is difficult to create a database dedicated to the process of evaluating the location of a failure in the hierarchically defined FF (Flip-Flop).
This is because the logical state of he input/output terminal of FF (Flip-Flop) relates to two or more time points, which makes the processing complicated.
Thus, the present invention was made in consideration of the foregoing problems, and an object of the present invention is to provide a system, a method, and a recording medium for evaluating the location of a failure, capable of eliminating the necessity of creating a database dedicated to the evaluation of the location of a failure.
Another object of the present invention is to provide a system, a method, and a recording medium for evaluating the location of a failure, capable of utilizing a circuitry hierarchically defined for logic simulation.
Another object of the present invention is to provide a system, a method, and a recording medium for evaluating the location of a failure, capable of eliminating the necessity of creating a database dedicated to the evaluation of a failure location of a novel FF. These and other objects, features and advantages of the present invention will become apparent to those skilled in the related art upon reading the following description.
In order to achieve the foregoing objects, in accordance with a first aspect of the invention, a system for evaluating the location of a failure is adapted to evaluate logical states of the input/output terminal of a target gate and the inside thereof, retrieve an unestablished gate and a terminal, a temporary logical value being set thereon, and set information regarding the related failure terminal of the input/output terminal by utilizing the circuitry of the target gate hierarchically described by a basic gate.
More specifically, the system for evaluating the location of a failure comprises: expected value setting device (23 in FIG. 1) for evaluating the logical states of the input/output terminal of the target gate and the inside thereof; logical state setting device (24 in FIG. 1); temporary decided line retrieving device (25 in FIG. 1) for retrieving a terminal of a target gate serving as a target, a temporary logical value being set thereon, when no logical contradiction occurs; and related failure terminal setting device (26 in FIG. 1) for transmitting information regarding the related failure terminal of the input/output terminal of the target gate to an input side.
According to the present invention, a circuit portion related to the failure output terminal is extracted, and a failure propagation path inside the circuit portion is evaluated. Further, when necessary, another circuit portion side is extracted in the input side, and all failure propagation paths are evaluated. Then, based on connection information of the evaluated paths, a priority order (a failure probability) is calculated among failure candidates on the path, and a list of a failure candidates in the logic circuit is output.
In accordance with a second aspect of the present invention, a system for evaluating the location of a failure is adapted to evaluate all failure propagation paths inside a target gate, obtain a terminal, a temporary logical value being set thereon, and a logical state at this time, and set information regarding the related failure terminal of an input/output terminal, by utilizing the circuitry of the target gate hierarchically described by a basic gate.
More specifically, the system for evaluating the location of a failure comprises: expected value setting device (23 in FIG. 7) for setting expected values of the input/output terminal of the target gate and the inside thereof; a failure propagation path evaluating device (27 in FIG. 7) for evaluating all failure propagation paths inside the target gate; and related failure terminal setting device (26 in FIG. 7) for transmitting information regarding the related failure terminal of the input/output terminal of the target gate to an input side.
In accordance with a third aspect of the invention, a system for evaluating the location of a failure is adapted to evaluate logical states of the input/output terminal of a target gate and the inside thereof at two time points, retrieve a terminal, a temporary logical value being set thereon, and set information regarding the related failure terminal of the input/output terminal, by utilizing the circuitry of the target gate hierarchically described by a basic gate and a basic FF.
More specifically, the system for evaluating the location of a failure comprises: basic FF retrieving device (31 in FIG. 9) for retrieving the basic FF inside the target gate; expected value setting device (23 in FIG. 9) for setting logical states of the input/output terminal of the target gate at two time points and the inside thereof; logical state setting device (24 in FIG. 9); second temporary decided line retrieving device (35 in FIG. 9) for retrieving a terminal serving as a target, a temporary logical value being set thereon, by referring to the logical states inside the target gate of the two time points, when no logical contradiction occurs; and second related failure terminal setting device (36 in FIG. 9) for transmitting information regarding the related failure terminal of the input/output terminal of the target gate to an input side by tracing a failure propagation path extending over the two time points.
According to the present invention, the expected value setting device calculates an expected value inside the target gate composed of the basic gate by referring to the expected value of the input/output terminal, entered from an input device, and the circuitry of the target gate stored in a logic circuitry storage unit, and then records this value in a logical state storage unit. The calculation of the expected value is carried out based on an IF-THEN operation in an output direction for obtaining an output state from an input state.
According to the present invention, the logical state evaluating device calculates a logical state inside the target gate composed of the basic gate by referring to the logical value of the input/output terminal, entered from the input device, and the circuitry of the target gate stored in the logic circuitry storage unit, and then records this state in the logical state storage unit. The calculation of the logical state is carried out based on an IF-THEN operation in an input/output direction.
According to the present invention, the temporary decided line retrieving device retrieves an unestablished gate inside the target gate by referring to the circuitry of the target gate stored in the logic circuitry storage unit, and the expected value and the logical state inside the target gate recorded in the logical state storage unit, and retrieves an input signal line, a logical state thereof having yet to be established in the unestablished gate. The device further retrieves the input terminal of the target gate, a temporary logical value being set thereon, by tracing a signal line having an unestablished logical state from the input signal line in an input direction.
According to the present invention, the related failure terminal setting device retrieves a failure output terminal in the target gate by referring to the circuitry of the target gate stored in the logic circuitry storage unit, and the expected value and the logical state inside the target gate recorded in the logical state storage unit, traces a failure propagation path, in which expected and logical values are different from each other, from the failure output terminal in the input direction, and then adds information regarding the related failure terminal, which is set in the failure output terminal in the output side of the failure propagation path, to the failure input terminal in the input side of the failure propagation path.
According to the present invention, the failure propagation evaluating device evaluates a logical state and a failure propagation path inside the target gate by referring to the circuitry of the target gate stored in the logic circuitry storage unit, and the expected value and the logical state inside the target gate recorded in the logical state storage unit.
According to the present invention, the basic FF retrieving device retrieves the basic FF of the circuit of the target gate by referring to the circuitry of the target gate stored in the logic circuitry storage unit, and then retrieves the position of the basic FF in the circuit.
According to the present invention, the second temporary decided line retrieving device retrieves an unestablished gate inside the target gate by referring to the circuitry of the target gate recorded in the logic circuitry storage unit, and the expected value and the logical state of the two time points inside the target gate recorded in the logical state storage unit, and retrieves an input signal line, a logical state thereof having yet to be established in the unestablished gate. This device further retrieves the input terminal of the target gate, a temporary logical value being set thereon, by tracing a signal line having a logical state unestablished from the input signal line in the input direction. When reaching at the basic FF during the tracing of the signal line, the tracing is continued going back in time by referring to the input clock signal of the basic FF.
According to the present invention, the second related failure terminal setting device retrieves a failure output terminal in the target gate by referring to the circuitry of the target gate recorded in the logic circuitry storage unit, and the expected value and the logical state of the two time points inside the target gate recorded in the logical state storage unit. Then, this device traces a failure propagation path, in which expected and logical values are different from each other, from the failure output terminal in the input direction, and then adds information regarding a related failure terminal set in the failure output terminal in the output side of the failure propagation path to the failure input terminal in the input side of the failure propagation path. When reaching at the basic FF during the tracing of the failure propagation path, the tracing is continued going back in time by referring to the input clock signal of the basic FF.